package main

import (
	"fmt"
	. "go_data_structures_and_algorithms/tool"
)

func main() {
	n1 := ListNode{Val: 1}
	n2 := ListNode{Val: 2}
	n3 := ListNode{Val: 3}
	n4 := ListNode{Val: 5}
	n5 := ListNode{Val: 9}
	n1.Next = &n2
	n2.Next = &n3
	n3.Next = &n4
	n4.Next = &n5
	n11 := ListNode{Val: 5}
	n21 := ListNode{Val: 4}
	n31 := ListNode{Val: 9}
	n41 := ListNode{Val: 4}

	n11.Next = &n21
	n21.Next = &n31
	n31.Next = &n41

	addition := ChainListAddition(&n11, &n1)
	fmt.Println(addition)

}

func ChainListAddition(l1, l2 *ListNode) *ListNode {
	llen := CountLength(l1)
	slen := CountLength(l2)
	var longlist *ListNode
	var shortlist *ListNode
	var long *ListNode
	carry := 0
	ValueNum := 0
	var LastNode *ListNode
	if llen >= slen {
		longlist = l1
		shortlist = l2
	} else {
		longlist = l2
		shortlist = l1
	}
	long = longlist
	for shortlist != nil {
		if carry == 1 {
			ValueNum = shortlist.Val + longlist.Val + carry
			carry--
		} else {
			ValueNum = shortlist.Val + longlist.Val
		}

		if (ValueNum / 10) == 1 {
			carry = 1
			longlist.Val = ValueNum % 10
		} else {
			longlist.Val = ValueNum
		}
		LastNode = longlist
		longlist = longlist.Next
		shortlist = shortlist.Next
		ValueNum = 0
	}

	for longlist != nil {
		if carry == 1 {
			ValueNum = longlist.Val + carry
			carry--
		} else {
			ValueNum = longlist.Val
		}

		if (ValueNum / 10) == 1 {
			carry = 1
			longlist.Val = ValueNum % 10
		} else {
			longlist.Val = ValueNum
		}
		LastNode = longlist
		ValueNum = 0
		longlist = longlist.Next
	}
	if carry != 0 {
		LastNode.Next = &ListNode{Val: carry}
	}
	return long

}

func CountLength(l1 *ListNode) int {

	len := 0
	if l1 != nil {
		len++
		for l1.Next != nil {
			len++
			l1 = l1.Next
		}
	}

	return len
}
